#include<iostream>
#include<vector>
using namespace std;
int* partision3(vector<int>& a,int left,int right)
{
    if(left > right)
        return new int[2]{-1,-1};
    if(left == right)
        return new int[2]{left,right}; 
    int less = left-1;
    int big = right;
    int index = left;
    while(index < big)
    {
        if(a[index] > a[right])
        {
            swap(a[index],a[--big]);
        }
        else if(a[index] < a[right])
        {
            swap(a[index++],a[++less]);
        }
        else
        {
            index++;
        }
    }
    swap(a[right],a[big]);
    return new int[2]{less+1,big};
}
void quick_sort(vector<int>& a,int left,int right)
{
    if(left >= right) 
        return ;
    int* p = partision3(a,left,right);
    quick_sort(a,left,p[0]-1);
    quick_sort(a,p[1]+1,right);
}
vector<int> MySort(vector<int>& arr) {
    // write code here
    quick_sort(arr,0,arr.size()-1);
    return arr;
}
int main()
{
    vector<int> v{9,8,7,6,5,4,3,2,1};
    v = MySort(v);
    for(auto& x:v)
        cout << x<<" ";
    cout << endl;
    return 0;
}